package com.shawn.datastructure.stack;

import java.util.Stack;

public class EvaluateReversePolishNotation {

	public int evalRPN(String[] tokens) {
		Stack<Integer> stack = new Stack<>();
		for (int i = 0; i < tokens.length; i++) {
			String token = tokens[i];
			if (isNum(token)) {
				stack.push(Integer.parseInt(token));
			} else {
				int x = stack.pop();
				int y = stack.pop();
				int result = 0;
				switch (token) {
					case "+":
						result = x + y;
						break;
					case "*":
						result = x * y;
						break;
					case "-":
						result = x - y;
						break;
					case "/":
						if (y != 0) {
							result = x / y;
						}
						break;
				}
				stack.push(result);
			}
		}
		return stack.peek();
	}

	public int cal(String[] tokens){
		Stack<Integer> numStack = new Stack<>();
		Stack<String> operateStack = new Stack<>();
		for (int i = 0; i < tokens.length; i++) {
			String token = tokens[i];
			if (isNum(token)) {
				numStack.push(Integer.parseInt(token));
			} else {
				// 如果比运算符栈顶元素的优先级高，就将当前运算符压入栈；
				// 如果比运算符栈顶元素的优先级低或者相同，从运算符栈中取栈顶运算符，
				// 从操作数栈的栈顶取 2 个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较。
				if(operateStack.isEmpty()){
					operateStack.push(token);
				}else{
					String c = operateStack.peek();
					if(c != null){
						switch (c){
							case "+": case "-":
								if("+".equals(token) || "-".equals(token)){
									while (!operateStack.isEmpty()){
										int x = numStack.pop();
										int y = numStack.pop();
										String s = operateStack.pop();
										numStack.push(cal(x,y,s));
									}
								}
								operateStack.push(token);
								break;
							case "*": case "/":
								while (!operateStack.isEmpty()){
									int x = numStack.pop();
									int y = numStack.pop();
									String s = operateStack.pop();
									numStack.push(cal(x,y,s));
								}
								operateStack.push(token);
								break;

						}
					}
				}
			}
		}
		while (!operateStack.isEmpty()){
			int x = numStack.pop();
			int y = numStack.pop();
			numStack.push(cal(x,y,operateStack.pop()));
		}
		return numStack.pop();
	}

	private int cal(int x,int y,String token){
		if("+".equals(token)){
			return x + y;
		}
		if("-".equals(token)){
			return y - x;
		}
		if("*".equals(token)){
			return x * y;
		}
		if("/".equals(token)){
			return y / x;
		}
		return 0;
	}

	private boolean isNum(String str) {
		String[] chars = {"+", "-", "*", "/"};
		for (int i = 0; i < chars.length; i++) {
			if (str.equals(chars[i])) {
				return false;
			}
		}
		return true;
	}

	public static void main(String[] args) {
		EvaluateReversePolishNotation evaluateReversePolishNotation = new EvaluateReversePolishNotation();
		String[] str = {"3",  "*", "8", "/","5","/","6"};
		System.out.println(evaluateReversePolishNotation.cal(str));
	}
}
